#include <vector>

//选择排序，平均时间复杂度O(n^2),空间复杂度O(1),不稳定
void Selection_sort(vector<int> &nums){
    for(int i = 0;i < nums.size()-1;i++){
        int min = nums[i], index = i;
        for(int j = i+1;j < nums.size()-1;j++){
            if(min > nums[j]){
                min = nums[j];
                index = j;
            }
        }
        int temp = nums[i];
        nums[i] = nums[index];
        nums[index] = temp;
    }
}